package com.leetcode.根据算法进行分类.数学定理相关;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/4/11
 * @description: 264. 丑数 II
 */
public class B_264_丑数_II {
    static B_264_丑数_II action = new B_264_丑数_II();

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    static void test1() {
        //
        int res = action.nthUglyNumberFasterAndElegant(37);
        System.out.println("res = " + res);
    }

    static void test2() {
        //

        //System.out.println("res = " + res);
    }

    static void test3() {
        //

        //System.out.println("res = " + res);
    }


    /**
     * 只能说是个笨方法了吧
     * 可以优化的地方：
     * 可以用一个变量缓存接下来2，3，5 对应的乘积
     * --
     * 6ms
     *
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        //int[] arr = new int[]{0, 1, 2, 3, 4, 5};
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        if (n <= 5) {
            return list.get(n);
        }
        int index2 = 3;
        int index3 = 3;
        int index5 = 5;
        int size = 5;
        while (size < n) {
            int min2 = list.get(index2) << 1;
            int min3 = list.get(index3) * 3;
            int min5 = list.get(index5) * 5;
            if (min2 <= min3 && min2 <= min5) {
                list.add(min2);
                index2++;
                //此时 min2 最小
                if (min2 == min3) {
                    //同时 min3 也是最小
                    index3++;
                }
                if (min2 == min5) {
                    index5++;
                }
            } else if (min3 <= min2 && min3 <= min5) {
                list.add(min3);
                index3++;
                //此时 min2 最小
                if (min2 == min3) {
                    //同时 min3 也是最小
                    index2++;
                }
                if (min3 == min5) {
                    index5++;
                }
            } else {
                list.add(min5);
                index5++;
                //此时 min2 最小
                if (min5 == min3) {
                    //同时 min3 也是最小
                    index3++;
                }
                if (min2 == min5) {
                    index2++;
                }
            }
            size++;
        }
        return list.get(n);
    }

    /**
     * dp[i] = Math.min(Math.min(num2, num3), num5);
     * if (dp[i] == num2) {
     * p2++;
     * }
     * if (dp[i] == num3) {
     * p3++;
     * }
     * if (dp[i] == num5) {
     * p5++;
     * }
     * --
     * 如果用上面的方式会更加优雅
     *
     * @param n
     * @return
     */
    public int nthUglyNumberFaster(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        if (n <= 5) {
            return list.get(n);
        }
        int index2 = 3;
        int index3 = 3;
        int index5 = 5;
        int size = 5;
        int next2 = 6, next3 = 9, next5 = 25;
        while (size < n) {
            int min2 = next2;
            int min3 = next3;
            int min5 = next5;
            if (min2 <= min3 && min2 <= min5) {
                list.add(min2);
                index2++;
                next2 = list.get(index2) << 1;
                //此时 min2 最小
                if (min2 == min3) {
                    //同时 min3 也是最小
                    index3++;
                    next3 = list.get(index3) * 3;
                }
                if (min2 == min5) {
                    index5++;
                    next5 = list.get(index5) * 5;
                }
            } else if (min3 <= min2 && min3 <= min5) {
                list.add(min3);
                index3++;
                next3 = list.get(index3) * 3;
                //此时 min2 最小
                if (min2 == min3) {
                    //同时 min3 也是最小
                    index2++;
                    next2 = list.get(index2) << 1;
                }
                if (min3 == min5) {
                    index5++;
                    next5 = list.get(index5) * 5;
                }
            } else {
                list.add(min5);
                index5++;
                next5 = list.get(index5) * 5;
                //此时 min2 最小
                if (min5 == min3) {
                    //同时 min3 也是最小
                    index3++;
                    next3 = list.get(index3) * 3;
                }
                if (min2 == min5) {
                    index2++;
                    next2 = list.get(index2) << 1;
                }
            }
            size++;
        }
        return list.get(n);
    }

    public int nthUglyNumberFasterAndElegant(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        if (n <= 5) {
            return list.get(n);
        }
        int index2 = 3;
        int index3 = 3;
        int index5 = 5;
        int size = 5;
        int next2 = 6, next3 = 9, next5 = 25;
        while (size < n) {
            int temp = Math.min(Math.min(next2, next3), next5);
            list.add(temp);

            if (temp == next2) {
                index2++;
                next2 = list.get(index2) << 1;

            }
            if (temp == next3) {
                index3++;
                next3 = list.get(index3) * 3;
            }
            if (temp == next5) {
                index5++;
                next5 = list.get(index5) * 5;
            }

            size++;
        }
        return list.get(n);
    }
}
